#include <algorithm>
#include <stdexcept>

#ifndef RATIONAL_
#define RATIONAL_

template<typename T>
class rational {
	T numenator, denominator;

	void normalize() {
		static const T zero = static_cast<T> (0);
		static const T one = static_cast<T> (1);
		if (denominator == zero) {
			throw std::domain_error("Negative denominator");
		}
		T gcd = std::__gcd(numenator, denominator);
		numenator /= gcd;
		denominator /= gcd;
		if (denominator < zero) {
			numenator *= -one;
			denominator *= -one;
		}
	}

public:
	rational(const T& num = static_cast<const T> (0), const T& den =
			static_cast<const T> (1)) :
		numenator(num), denominator(den) {
		normalize();
	}

	rational(const rational & r) :
		numenator(r.numenator), denominator(r.denominator) {
	}

	T get_numenator() const {
		return numenator;
	}

	T get_denominator() const {
		return denominator;
	}

	template<typename T2>
	rational& operator=(const rational<T2> &r) {
		numenator = static_cast<T> (r.get_numenator());
		denominator = static_cast<T> (r.get_denominator());
	}

	template<typename T2>
	rational& operator=(const T2 &a) {
		*this = rational<T> (static_cast<T> (a));
	}

	template<typename T2>
	rational& operator +=(const rational<T2> & r) {
		numenator = numenator * r.get_denominator() + denominator
				* r.get_numenator();
		denominator = denominator * r.get_denominator();
		normalize();
		return *this;
	}
	template<typename T2>
	rational& operator +=(const T2& r) {
		return *this += rational<T2> (r);
	}

	template<typename T2>
	rational& operator -=(const rational<T2> & r) {
		numenator = numenator * r.get_denominator() - denominator
				* r.get_numenator();
		denominator = denominator * r.get_denominator();
		normalize();
		return *this;
	}
	template<typename T2>
	rational& operator -=(const T2& r) {
		return *this -= rational<T2> (r);
	}

	template<typename T2>
	rational& operator *=(const rational<T2> & r) {
		numenator *= r.get_numenator();
		denominator *= r.get_denominator();
		normalize();
		return *this;
	}
	template<typename T2>
	rational& operator *=(const T2& r) {
		return *this *= rational<T2> (r);
	}

	template<typename T2>
	rational& operator /=(const rational<T2> & r) {
		numenator *= r.get_denominator();
		denominator *= r.get_numenator();
		normalize();
		return *this;
	}
	template<typename T2>
	rational& operator /=(const T2& r) {
		return *this /= rational<T2> (r);
	}

	rational& operator++() {
		numenator += denominator;
		normalize();
		return *this;
	}

	rational& operator--() {
		numenator -= denominator;
		normalize();
		return *this;
	}

	const rational operator++(int) {
		rational ans = *this;
		++*this;
		return ans;
	}

	const rational operator--(int) {
		rational ans = *this;
		--*this;
		return ans;
	}

	template<typename T2>
	operator T2() const {
		return static_cast<T2> (numenator) / denominator;
	}

	template<typename T2, typename T3>
	friend bool operator ==(const rational<T2>&, const rational<T3>&);
	template<typename T2, typename T3>
	friend bool operator ==(const rational<T2>&, const T3&);
	template<typename T2, typename T3>
	friend bool operator ==(const T2&, const rational<T3>&);
	template<typename T2, typename T3>
	friend bool operator <(const rational<T2>&, const rational<T3>&);
	template<typename T2, typename T3>
	friend bool operator <(const rational<T2>&, const T3&);
	template<typename T2, typename T3>
	friend bool operator <(const T2&, const rational<T3>&);
};

template<typename T1, typename T2>
inline bool operator <(const rational<T1>& a, const rational<T2>& b) {
	return a.numenator * b.denominator < b.numenator * a.denominator;
}
template<typename T1, typename T2>
inline bool operator <(const rational<T1>& a, const T2& b) {
	return a < rational<T2> (b);
}
template<typename T1, typename T2>
inline bool operator <(const T1& a, const rational<T2>& b) {
	return rational<T1> (a) < b;
}

template<typename T1, typename T2>
inline bool operator ==(const rational<T1>& a, const rational<T2>& b) {
	return a.numenator == b.numenator && a.denominator == b.denominator;
}
template<typename T1, typename T2>
inline bool operator ==(const rational<T1>& a, const T2 & b) {
	return a.numenator == b * a.denominator;
}
template<typename T1, typename T2>
inline bool operator ==(const T1& a, const rational<T2>& b) {
	return b.numenator == b.denominator * a;
}

template<typename T1, typename T2>
inline bool operator !=(const rational<T1>& a, const rational<T2>& b) {
	return !(a == b);
}
template<typename T1, typename T2>
inline bool operator !=(const rational<T1>& a, const T2 b) {
	return !(a == b);
}
template<typename T1, typename T2>
inline bool operator !=(const T1& a, const rational<T2>& b) {
	return !(a == b);
}

template<typename T1, typename T2>
inline bool operator <=(const rational<T1>& a, const rational<T2>& b) {
	return a < b || a == b;
}
template<typename T1, typename T2>
inline bool operator <=(const T1& a, const rational<T2>& b) {
	return a < b || a == b;
}
template<typename T1, typename T2>
inline bool operator <=(const rational<T1>& a, const T2& b) {
	return a < b || a == b;
}

template<typename T1, typename T2>
inline bool operator >(const rational<T1>& a, const rational<T2>& b) {
	return b < a;
}
template<typename T1, typename T2>
inline bool operator >(const T1& a, const rational<T2>& b) {
	return b < a;
}
template<typename T1, typename T2>
inline bool operator >(const rational<T1>& a, const T2& b) {
	return b < a;
}

template<typename T1, typename T2>
inline bool operator >=(const rational<T1>& a, const rational<T2>& b) {
	return b <= a;
}
template<typename T1, typename T2>
inline bool operator >=(const T1& a, const rational<T2>& b) {
	return b <= a;
}
template<typename T1, typename T2>
inline bool operator >=(const rational<T1>& a, const T2& b) {
	return b <= a;
}

template<typename T>
inline rational<T> operator -(const rational<T> r) {
	return rational<T> () - r;
}

template<typename T1, typename T2>
inline rational<T1> operator +(const rational<T1> & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans += r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator +(const rational<T1> &r1, const T2 & r2) {
	return r1 + rational<T2> (r2);
}
template<typename T1, typename T2>
inline rational<T1> operator +(const T1 &r1, const rational<T2> & r2) {
	return rational<T1> (r1) + r2;
}

template<typename T1, typename T2>
inline rational<T1> operator -(const rational<T1> & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans -= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator -(const T1 & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans -= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator -(const rational<T1> & r1, const T2 & r2) {
	rational<T1> ans = r1;
	ans -= r2;
	return ans;
}

template<typename T1, typename T2>
inline rational<T1> operator *(const rational<T1> & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans *= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator *(const T1 & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans *= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator *(const rational<T1> & r1, const T2 & r2) {
	rational<T1> ans = r1;
	ans *= r2;
	return ans;
}

template<typename T1, typename T2>
inline rational<T1> operator /(const rational<T1> & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans /= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator /(const T1 & r1, const rational<T2> & r2) {
	rational<T1> ans = r1;
	ans /= r2;
	return ans;
}
template<typename T1, typename T2>
inline rational<T1> operator /(const rational<T1> & r1, const T2 & r2) {
	rational<T1> ans = r1;
	ans /= r2;
	return ans;
}

#endif /*RATIONAL_ */
